This invention relates to a layout compaction system as used in designing a layout of VLSI or another layout on a printed circuit board, and, in particular, to the compaction system which can automatically provide a small-sized VLSI.
The VLSI has been of high density, so that human can no longer manually design the VLSI. To aid the designing of the VLSI, some kind of EDA (electronic design automation) tools are used in the art of the VLSI design. Especially, layout compaction systems are adapted to automatically compact a circuit layout and work in a layout design phase.
In general, the circuit layout is formed on a substrate and comprises a plurality of layers on each of which objects are arranged as a layer pattern. When the objects are moved in a certain direction, free space is obtained in the opposite direction and enables the layout compaction system to compact the circuit layout. Such objects will be called moving objects, hereinafter.
In detail, the moving objects comprise components, wires, via-holes, semiconductor cells, and so on. Among them, some of the wires are laid on the respective layers in bundles, and some of the components extend over layers. Although each of the components has terminals, all terminals belonging to one component may exist on layers.
The layout compaction system requires taking the complicated structure of the circuit layout into consideration, otherwise the compacted circuit layout may not perform correctly. Besides, there is requirement for the compaction to be high rate. To respond these requirements, various kinds of the compacting methods have been developed and proposed.
In some of the proposed methods, the circuit layout is compacted by moving components as moving objects in relation with each other.
One of them relates to two-dimensional compaction, where the components are simultaneously moved in two directions. Such compacting method is, for example, disclosed in xe2x80x9cTwo-Dimensional Compaction by xe2x80x98Zone Refiningxe2x80x99: Hynchul Shin, Alberto L. Sangiovanni-Vincentelli, Carlo H. Sequin; Proc. of 23rd Design Automation Conference, 1986, pp. 115-122.xe2x80x9d In summary, the compacting method moves the semiconductor cells in a vertical direction of the circuit layout from upper side one to down, and simultaneously moves the semiconductor cells in a horizontal direction of the circuit layout.
Another compacting method is disclosed in Japanese Unexamined Patent Publication No. Hei 5-274392, namely, JP-A 5-274392. In this method, the substrate is divided at positions of wires into a plurality of regions. That is, on all boundaries between the regions, the wires are always laid. Under the condition, the compaction in the horizontal direction is executed from the regions closer to the left side of the substrate to right, and simultaneously the compaction in the vertical direction is executed from the regions closer to the upper side of the substrate to down. Thus, the method keeps an arrangement of the regions, and provides uniformly compacted circuit layout.
However, the above-mentioned methods can not handle wiring of the diagonal form, and therefore, can not accomplish the high rate of the compaction.
On the other hand, the method which can handle wiring of the diagonal form, is disclosed in Japanese Unexamined Patent Publication (JP-A) No. Hei 10-3491, namely, JP-A 10-3491. This method removes all of the wires from the circuit layout, and then, compacts the circuit layout by moving the component together with re-wiring of newly wires.
It is however noted that the newly wires bring about another problem since consideration has been made about only the moving of the component. Some of wires are laid on the layers in bundle to form wire bundle. If not taking the characteristic of the circuit into consideration, the wire bundle has a width substantially equal to the total sum of the width of the wires comprising the wire bundle. Actually, predetermined margins however are required between the adjacent wires, to prevent cross talk from occurring between the adjacent wires. Such margins are fixed in the design rule for the compaction targets, such as the VLSI. The above method of JP-A 10-3491 does not consider such characteristic, and thereby, may violate the design rule.
This invention therefore provides a compacting method which can handle wiring of the diagonal form with a relationship of the components and the wires kept, and which can meet the design rule.
According to one aspect of this invention, a compacting method compacts a circuit layout having a plurality of layers on which moving objects form layer patterns. For example, the moving objects comprise components having terminals, wires, via-holes, semiconductor cells, conductors having predetermined pattern shapes. In this specification, parts of the via-hole at every layer, the semiconductor cells, profiles of the components may be handled as the terminal. A combination unit of the component and the via-hole may be, as a whole, handled as single component. The via-hole connected to only wire may be handled as one of the components. The conductors may be approximated into polygons, each of the polygons being handled as the component, while edges of each polygon begin handled as the terminals. These handling are for the sake of clarity and for readily processing, which do not restrict this invention.
Some of the wires are laid on the respective layers in bundles to form wire bundles. Each of the wires having a wire width and a pattern shape as a wire pattern shape. Each of the wire bundles having a pattern shape as a bundle pattern shape and a bundle width which is defined by a total width of wires comprising each wire bundle.
The method comprises the following three steps for each of the layer patterns on each of the layers.
First, a graph problem is assumed under first through fourth condition, wherein a graph comprises nodes corresponding to the components and edges corresponding to moving vectors of the components. The first condition is that the wire widths of the wires are fixed at constant wire width values. The second condition is that belt widths of wire belts are fixed at constant belt width values. The wire belts are defined by adding predetermined margins to both sides in a width direction of each of the wire bundles in compliance with a design rule. Each of the belt widths is equal to a sum of each of the bundle widths and the predetermined margins. The third condition is that component-wire spaces are variable. Each of the component-wire spaces is defined to be a distance from the component to edges in the width direction of the wire belts and/or the wires. The fourth condition is that wire pattern shape and the bundle pattern shape are changeable for compacting.
When assumed, the graph problem is solved so that a moving order, a moving direction, and a moving distance of each component are determined for moving the components. And then, each component is moved according to the moving order, the moving direction and the moving distance.
With this method, the compacted circuit layout does not have the problem, such as cross talk, because the assumption of the graph problem takes the design rule into consideration and, as the solution, the moving vectors of the components are determined. The method may be in the form of software instructions and be executed on a computer (or by a processor) virtually. In this case, the computer applies the method original layout data of the circuit layout to produce compacted layout data of the compacted circuit layout.